Distance geometry

Distance geometry is the characterization and study of sets of points based only on given values of the distances between member pairs. Therefore distance geometry has immediate relevance where distance values are determined or considered, such as in surveying, cartography and physics.

Contents

Introduction

The Distance Geometry Problem (DGP) is the problem of finding the coordinates of a set of points starting from the distances between pairs of such points,[1][2][3][4],.[5] Such a problem is nowadays much studied by the scientific community, because there are real-life applications that lead to the formulation of a DGP. As an example, an interesting application is the problem of locating sensors in telecommunication networks. In such a case, the positions of some sensors are known (which are called anchors) and some of the distances between sensors (which can be anchors or not) are known: the problem is to locate the positions of all the sensors.

Many other real-life applications that can be formulated as DGPs arise in biology and chemistry. For example, some models for protein predictions are based on a DGP, and also some models for protein docking. However, in this field, the most studied problem is the following. The coordinates of the atoms of a given molecular conformation are to be discovered by exploiting only some of the distances between pairs of atoms found by experimental techniques. If this is the case, the problem is known in the literature as the Molecular Distance Geometry Problem (MDGP).

Discussion

A straight line is the shortest path between two points. Therefore the distance from A to B is no bigger than the length of the straight-line path from A to C plus the length of the straight-line path from C to B. This fact is called the triangle inequality. If that sum happens to be equal to the distance from A to B, then the three points A, B, and C lie on a straight line, with C between A and B.

Similarly, suppose one knows

Knowing only these six numbers, one would like to figure out

Distance geometry includes the solution of such problems.

Cayley–Menger determinants

Of particular utility and importance are classifications by means of Cayley–Menger determinants, named after Arthur Cayley and Karl Menger:

 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & 1 \\
       1 &       1 &       1 & 0
\end{bmatrix} = 0,
 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & d(BD)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & d(CD)^2 & 1 \\
 d(AD)^2 & d(BD)^2 & d(CD)^2 &       0 & 1 \\
       1 &       1 &       1 & 1       & 0
\end{bmatrix} = 0,
but not all triples of elements of Π are straight to each other;
 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & d(AE)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & d(BD)^2 & d(BE)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & d(CD)^2 & d(CE)^2 & 1 \\
 d(AD)^2 & d(BD)^2 & d(CD)^2 &       0 & d(DE)^2 & 1 \\
 d(AE)^2 & d(BE)^2 & d(CE)^2 & d(DE)^2 &       0 & 1 \\
       1 &       1 &       1 & 1       &       1 & 0
\end{bmatrix} = 0,
but not all quadruples of elements of Φ are plane to each other;

and so on.

Software for distance geometry

References

  1. ^ Blumenthal, L.M. (1970). Theory and applications of distance geometry (2nd ed.). Bronx, New York: Chelsea Publishing Company. pp. 347. ISBN 0-8284-0242-6. LCCN 79113117. 
  2. ^ Crippen, G.M.; Havel, T.F. (1988). "Distance Geometry and Molecular Conformation". John Wiley & Sons. 
  3. ^ Liberti, L.; Lavor, C.; Maculan, N. (2008). "A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem". International Transactions in Operational Research 15: 1–17. 
  4. ^ Mucherino, A.; Liberti, L.; Lavor, C.; Maculan, N. (2009). "Comparisons between an Exact and a MetaHeuristic Algorithm for the Molecular Distance Geometry Problem". ACM Conference Proceedings, Genetic and Evolutionary Computation Conference (GECCO09): 333–340. 
  5. ^ More, J.J.; Wu, Z. (1999). "Distance Geometry Optimization for Protein Structures". Journal of Global Optimization 15: 219–223. 

See also